/*
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
*/

class Solution {
public:
    void calcStairs(int i, vector<int> &v) {
        if (i==1) {v[i] = 1; return;}
        if (i==2) {v[i] = 2; return;}
        if (!v[i-1]) calcStairs(i-1, v);
        if (!v[i-2]) calcStairs(i-2, v);
        v[i] = v[i-1] + v[i-2];
    }
    int climbStairs(int n) {
        if (!n) return 0;
        vector<int> res(n+1, 0);
        calcStairs(n, res);
        return res[n];
    }
};

/*
 * Iterative version
 */

/*
class Solution {
public:
    int climbStairs(int n) {
        int f_n, f_n2 = 1, f_n1 = 2;
        if (n <= 0) return 0;
        else if (n == 1) return f_n2;
        else if (n == 2) return f_n1;
        for (int i = 3; i <= n; i++) {
            f_n = f_n2 + f_n1;
            f_n2 = f_n1;
            f_n1 = f_n;
        }
        return f_n;
    }
};
*/
